package com.zjsru.plan2023.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: CookLee
 * @Date: 2023/4/29
 * <p>
 * 删除字符使频率相同
 * <p>
 * 输入：word = "abcc" 输出：true 解释：选择下标 3 并删除该字母，word 变成 "abc" 且每个字母出现频率都为 1 。
 * <p>
 * 输入：word = "aazz" 输出：false 解释：我们必须删除一个字母，所以要么 "a" 的频率变为 1 且 "z" 的频率为 2 ，要么两个字母频率反过来。所以不可能让剩余所有字母出现频率相同。
 * <p>
 * 恰好删除一个字母，不能一个字母都不删除。
 */
public class EqualFrequency {
    
    /**
     * 相等频率
     *
     * @param word 词
     * @return boolean
     */
    public boolean equalFrequency(String word) {
        //统计字符串的出现次数
        int[] charCount = new int[26];
        for (char c : word.toCharArray()) {
            charCount[c - 'a']++;
        }
        //使用哈希表存储出现次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int c : charCount) {
            //只存储出现过的字符
            if (c > 0) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
        }
        for (int c : charCount) {
            //字符未出现
            if (c == 0) {
                continue;
            }
            //更新字符出现的频率
            map.put(c, map.get(c) - 1);
            //当出现过的字符计数为0时 移除map 不在统计
            if (map.get(c) == 0) {
                map.remove(c);
            }
            //删除一个后，频率就从 c 变成了 c−1
            if (c - 1 > 0) {
                map.put(c - 1, map.getOrDefault(c - 1, 0) + 1);
            }
            //符合题意要求
            if (map.size() == 1) {
                return true;
            }
            //不只有一个不同的频率，则该方法从 map 中删除更新的计数-1
            if (c - 1 > 0) {
                map.put(c - 1, map.get(c - 1) - 1);
                if (map.get(c - 1) == 0) {
                    map.remove(c - 1);
                }
            }
            //说明删除当前字符不可行，我们把这个字符的频率就从 c−1变成 c，更新哈希表进行还原。
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        return false;
    }
    
    public static void main(String[] args) {
        EqualFrequency equalFrequency = new EqualFrequency();
        String word = "abcc";
        System.out.println(equalFrequency.equalFrequency(word));
    }
}
